
public class LongestIncreasingSubsequence {
	public void solve(int[] seq) {
		int length = seq.length;
		int[] len = new int[length];
		int[] lastIndex = new int[length];
		int[] endingIndex = new int[length];
		for (int i = 0; i < lastIndex.length; i++) {
			len[i] = 1;
			lastIndex[i] = -1;
			endingIndex[i] = i;
		}
		for (int i = 1; i < length; i++) {
			for(int j = 0; j < i; j++) {
				if (seq[i] > seq[endingIndex[j]]) {
					if (len[j] + 1 > len[i]) {
						len[i] = len[j] + 1;
						lastIndex[i] = endingIndex[j];
					}
				} else {
					if (len[j] > len[i]) {
						len[i] = len[j];
						lastIndex[i] = lastIndex[j];
						endingIndex[i] = endingIndex[j];
					}
				}
			}
		}
		
		System.out.println(len[length - 1]);
		int ending = length - 1;
		int cur = -1;
		do {
			cur = endingIndex[ending];
			System.out.println(seq[cur]);
//			ending = lastIndex[cur];
			ending = lastIndex[ending];
		} while (ending != -1);
	}
	
	public static void main(String[] args) {
		LongestIncreasingSubsequence test = new LongestIncreasingSubsequence();
		int[] input = //{5, 4, 3, 2, 1, 0};
			//{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
			{ 8, 6, 5, 1, 9, 3, 7, 4, 2, 10 };
		test.solve(input);
	}
}
